1. Field of the Invention
The invention relates to the placement of functional cells during integrated circuit design, and more particularly, to the use of timing information in the course of cell placement during computer automated circuit design.
2. Description of the Related Art
There is a burgeoning demand for smaller, faster, more versatile and more powerful integrated circuits (ICs) in a wide range of fields such as computing, communications, instrumentation, and control systems, for example. Advances in semiconductor technology have made it possible to construct transistors with dimensions that are so small that a single tiny IC chip can contain upwards of millions of transistors. The tremendous complexity of ICs requires the use of automated design tools to permit circuit designers to specify circuit functionality, to place the functional cells (e.g., transistors, circuit elements, objects or logic gates) on a floorplan of an IC chip, to route interconnecting wires between the placed cells and to test the resulting design to ensure that it meets requirements such as timing constraints.
Modern circuit design has evolved into a specialized field often referred to as electronic design automation in which computers and computer aided design (CAD) techniques are used to automate the IC chip design process. Computers can be programmed to reduce or decompose large, complicated circuit designs into a multitude of much simpler circuit design components. Computers can be programmed to develop an overall circuit design through a process of iterative solution of a multiplicity of smaller design problems that relate to the circuit design components. The computers can be programmed so that the design problems that relate to the circuit design components are solved so that design constraints for the overall circuit design are satisfied and the solution of the many smaller design problems results in convergence upon an acceptable overall circuit design.
Generally, an IC circuit design process begins with an engineer specifying the input/output signals, functionality and performance characteristics of the circuit. This information is provided to a computer that runs a logic synthesis program that generates a specification defining the integrated circuit in terms of a particular technology (e.g., very large scale integration). More specifically, the specification may include a netlist that specifies the interconnection of functional cells in the circuit. The specification serves as a template for the design of a physical embodiment of the circuit in terms of transistors, routing input and output pins, wiring and other features involved in the layout of the chip. The layout is a geometric or physical description of the IC that may consist of a set of geometric shapes in several layers.
An IC chip layout is designed by providing the specification to a computer that runs computer aided design programs that determine an optimal placement of functional cells and an efficient interconnection or routing scheme between cells to achieve the specified functionality. Computer implemented placement algorithms assign locations to the functional cells so that they do not overlap, so that chip area usage is optimized and so that interconnect distances are minimized. Chip area optimization permits more functional cells to fit into a given chip area. Wire length minimization reduces capacitive delays associated with longer nets so as to speed up the operation of the chip. Routing generally follows placement. Computer implemented routing algorithms determine the physical distribution of wire interconnects through the available space.
There are a number of different procedures for achieving optimal placement. The paper entitled, xe2x80x9cA Procedure for Placement of Standard-Cell VLSI Circuits,xe2x80x9d published in IEEE Transactions on Computer-Aided Design, Vol. CAD-4, No. 1, January 1985, by Alfred E. Dunlop and Brian W. Kernighan, proposes one such placement procedure. The method is based on graph partitioning to identify groups of modules that should be close to each other, and a technique for properly accounting for external connections at each level of partitioning.
The paper entitled, xe2x80x9cPROUD: A Fast Sea-of-Gates Placement Algorithm,xe2x80x9d published in the 25th ACM/IEEE Design Automation Conference (1988), Paper 22.3, by Ren-Song Tsay, Ernest S. Kuh and Chin-Ping Hsu, describes a placement process that takes advantage of the inherent scarcity in the connectivity specification of an integrated circuit design. The method solves repeatedly sparse linear equations by the successive over-relation process in a top-down hierarchy. More specifically, the technique uses a quadratic placement formulation. It takes I/O pad specification as input and solves successive linear sparse equations. It depends upon the concept of resistive network optimization.
The paper entitled, xe2x80x9cGORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization,xe2x80x9d published in IEEE Transactions on Computer-Aided Design, Vol. 10, No. 3, March 1991, by Jurgen M. Kleinhans, Georg Sigl, Frank M. Johannes, and Kurt Antreich, describes look-ahead methods incorporated in quadratic programs to hierarchically resolve routing congestion and reduce overall design area. The acronym GORDION stands for the two main parts of the method: global optimization and rectangle dissection, which is based on improved partitioning schemes. FIG. 1, taken from the paper by Kleinhans et al., shows overall data flow in the placement procedure of GORDION. The placement problem is formulated as a sequence of quadratic programming problems derived from the entire connectivity information of the circuit. Partitioning is employed to recursively create smaller and smaller placement subproblems. An increasing number of constraints restricting freedom of movement of the cells are imposed, reflecting successively refined partitioning. In this way, at each level of refinement, a global placement of cells is obtained simultaneously for all subproblems, avoiding any dependence on processing sequence.
U.S. Pat. No. 5,267,176 entitled, Method of Placing Modules on a Carrier, which issued on Nov. 30, 1993, to Antreich et al., describes a method that employs quadratic optimization. The method involves repetition of a global placement of cells on a placement region and subsequent partitioning. The global placement and partitioning steps are repeated until every sub-region contains at most a prescribed number of cells. The global placement ensues by arranging cells in the sub-regions such that the cells assigned to the sub-regions have their centers of gravity falling onto center coordinates of these sub-regions. The arrangement of all cells in all sub-regions is thereby simultaneously calculated. The sub-regions are defined by partitioning the placement region or, respectively, sub-regions, whereby a selectable number of cells are allocated to the sub-regions defined by partitioning.
U.S. Pat. No. 5,818,729 entitled, Method and System for Placing Cells using Quadratic Placement and a Spanning Tree Model, which issued on Oct. 6, 1998 to Chi-Hung Wang and Dwight D. Hill, discloses a placement method that uses a conjugate-gradient quadratic formula based placement system (e.g., GORDION) which inputs an integrated circuit design in a netlist form and generates a connectivity matrix for each multi-pin net within the design. The GORDION placement system performs global optimization using a conjugate gradient process to minimize wire lengths of circuit elements in nets. Partitioning also is performed. The clique model of a multi-pin net is used to generate first (or initial) connectivity matrices for the multi-pin nets which run through the global connectivity process. This first run provides a rough placement of the elements of the multi-pin nets. A spanning tree process is then run on the initial rough placement data and subsequent connectivity matrices are constructed using the spanning tree model, not the clique model, for multi-pin nets of within a defined size range. A placed netlist is the end product.
Ordinarily, as a chip design is developed, it is evaluated to ensure that it will satisfy timing constraints. An engineer typically specifies timing constraints such as signal arrival times at input and output pin terminals. In the course of developing the IC chip design, an incipient design is tested using automated timing verification tools to ascertain whether or not a design is likely to meet all of the timing constraints.
For example, U.S. Pat. No. 5,841,672 entitled, Method and Apparatus for Verifying Signal Timing of Electrical Circuits, issued Nov. 24, 1998 to Spyrou et al., discloses taking into account both resistance and capacitance of an interconnect network when determining both gate delays and interconnect delays of an integrated circuit. The time required for a signal to propagate through a component such as a gate typically is referred to as gate delay. The delay associated with interconnect wires that connect one gate to another is typically referred to as interconnect delay. A gate, for example, may comprise any device for processing a signal waveform, such as a logic gate (e.g., AND gate, OR gate, NAND gate and so forth) or even a single transistor. Interconnect delay depends on the resistance and conductance of the conductive paths between gates. Interconnect delay also depends upon driving characteristics of the gate or gates which are used to drive the conductive path between gates. As used herein, driving characteristics of a gate can be considered to include the slope of a gate output signal when the gate is transitioned from one value to another (e.g., logic level xe2x80x9c1 xe2x80x9d to logic level xe2x80x9c0xe2x80x9d or vice versa).
Generally, upon completion of cell placement and routing, often referred to as physical design, analyses involving RC extraction, timing and signal integrity evaluations are performed on the physical design (placed and routed design) to determine whether the specified timing constraints have been satisfied. It will be appreciated that after the placement and routing processes, an incipient physical design exists for the proposed circuit. The physical design may possess far more accurate RC delay information than the logical design used at the outset of the placement process. As a result, there frequently are significant discrepancies between the timing specified in a logical design and in the actual timing of the incipient physical design. Back-annotation often has been used to feed back more accurate RC information about the delay characteristics of critical nets to a logic optimizer or re-synthesis tool, for example, which can run another pass incorporating the new delay information. The back-annotated RC information, for example, might be used to add drivers to unexpectedly long wires or to optimize gates driving long wires or to optimize the paths that slowed them.
The gap between a logical design and physical design has become a more significant problem as circuit dimensions have reached the deep submicron level. Advances in semiconductor technology have resulted in ever-smaller dimensions of the gates and interconnect paths of integrated circuits. As gate sizes have decreased and interconnect paths have been developed with reduced cross-sectional area, the RC delay contribution of these conductive paths has become a more significant consideration in the estimation of signal delays through an integrated circuit. Traditional placement and routing tools obtain timing constraints from a logic synthesis tool. If the timing constraints are too conservative, then it can be difficult for the placement tool to determine which nets within a netlist to optimize. If the constraints are too aggressive, then it can be difficult to find non-critical nets whose performance can be sacrificed in order to improve the performance of other nets. The result in either case can be a less than optimal placement result.
Moreover, prior placement techniques often relied upon a statistical wire load model to estimate the RC delay of nets within a circuit design. In circuit designs in which the interconnect wires contribute a significant portion of the circuit delay, however, a statistical model becomes increasingly less accurate as the placement process progresses since it fails to account for more accurate RC delay information that becomes available in the course of the placement process. As a result, prior placement processes often do not lead to sufficiently accurate timing results to efficiently achieve timing convergence between logical and physical designs.
Thus, there has been a need for improvement in the placement of functional cells in integrated circuit designs. Specifically, there is a need for more efficient timing convergence between logical and physical designs in the course of cell placement. The present invention meets this need.
There is also a need for improvements in the detailed placement process that typically follows global placement. Global placement ordinarily involves an effort to place all functional cells so as to achieve a xe2x80x9clegalxe2x80x9d placement in which cells do not physically overlap other cells. Detailed placement involves an effort to optimize the placement result by moving cell locations in order improve circuit performance. More specifically, detailed placement may involve moving cells around a placement area in order improve routing by reducing routing congestion or to improve timing by reducing path delays. Detailed placement decisions often involve an exhaustive search for improved cell placement. Heuristics may be employed during detailed placement to evaluate whether or not a change in cell placement will result in improved performance. For example, a move that degrades local performance may nevertheless be implemented if it is likely to improve overall circuit performance. Determinations of which possible cell movements actually improve circuit performance can involve time consuming timing calculations, especially if the detailed placement involves an exhaustive search during which a multitude of possible cell movements are evaluated.
One solution to the problem of evaluating congestion or wire interconnect density during detailed placement involves the use of bounding boxes. For example, U.S. Pat. No. 5,587,923 entitled, Method for Estimating Routability and Congestion in a Cell Placement for Integrated Circuit Chip, issued Dec. 24, 1996 to Donald C. Wang, proposes estimating routing density in a placement by superimposing a pattern of contiguous tiles over the placement with each of the tiles having edges. Bounding boxes are constructed around nets respectively, and net probable densities are calculated within each bounding box for the wiring required by each net for each edge.
One solution to the problem of evaluating signal delay involves the use of slack budgets. A slack budget may prescribe the amount of delay that can be added to a net pin pair along a path in a circuit design without violating specified timing constraints for the circuit design. For instance, a user may specify a set of signal arrival times on primary input pins and corresponding output pins. The slack is the difference between the required arrival time on a primary output pin and the actual signal arrival time on the primary output pin. A positive slack time on a path, from a primary input to a primary output, signifies that the path satisfies the specified timing constraint because the timing delay on the path is less than that required by the timing constraint. A negative slack time on a path, from a primary input to a primary output, signifies that the path does not satisfy the specified timing constraint because the delay on the path is greater than the that required by the timing constraint. The merits of a proposed cell movement are evaluated based upon whether or not the move will cause a path that includes the cell to violate a slack budget constraint.
Unfortunately, there have been shortcomings with the use of slack budgets to evaluate detailed placement alternatives. For example, if the initial timing constraints are too conservative (i.e., too tight), then the detailed placement process may be overly constrained in trying alternative cell movements. On the other hand, if the timing constraints are not conservative enough, then the detailed placement process may vacillate among too many alternative cell movements without converging upon an optimal design quickly enough.
U.S. Pat. No. 5,831,863 entitled, Advanced Modular Cell Placement System with Wire Length Driven Affinity System, issued Nov. 3, 1998, to Scepanovic, et al. addresses wire length and density issues as part of the detailed placement process. A system for determining the affinity associated with the relocation of a cell located on a surface of a semiconductor chip to a different location on the surface is disclosed. Each cell may be part of a cell net containing multiple cells. The system initially defines a bounding box containing all cells in the net which includes the cell. The system then establishes a penalty vector based on the bounding box and borders of a region containing the cell, computes a normalized sum of penalties for all nets having the cell as a member, and calculates the affinity based on the normalized sum of penalties. The advanced cell placement system disclosed by Scepanovic, et al. patent aims to derive a legal placement with good wire length and density optimization. However, it does not address the timing driven placement issues.
Thus, there exists a need to improve the evaluation of how cell movements during detailed placement will affect signal delay in a circuit design. The present invention meets this need.
In one aspect, the present invention provides a novel global placement process and associated computer software for global placement of functional cells of an integrated circuit design. The global placement process is recursive and timing driven. Functional cells are placed according to how that placement is likely to influence signal timing. The global placement process is recursive. As more up to date cell placement information becomes available in the course of the global placement process, more up to date timing information is developed to guide further cell placement.
In another aspect, the present invention provides a novel detailed placement process and associated computer software for detail placement of functional cells of an integrated circuit design. Target zones are defined which provide indications of the timing impact of functional cell movement. A detailed search for improved cell placements is conducted in which target zones are used to assess the signal timing impact of proposed cell movements.
In another aspect, the present invention provides a novel process and associated computer software in which the novel global placement produces a global cell placement result, and the novel detailed placement process produces an improved detailed placement result.